package algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @功能
 * @创建时间 2020/5/17
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1,8,6,2,5,4,8,3,7};
//        sorte(arr);
//        print(arr);
        int[] strs = {2,2,2,2};
        isValid("(){}[]");
    }
    public static boolean isValid(String s) {
        Stack stack = new Stack();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '}' && stack.peek().equals("{")){
                stack.pop();
            }else if (chars[i] == ']' && stack.peek().equals("[")){
                stack.pop();
            } else if (chars[i] == ')' && stack.peek().equals("(")) {
                stack.pop();
            }else {
                stack.push(String.valueOf(chars[i]));
            }

        }
        return stack.isEmpty();

    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int first = 0; first < len - 3; first++) {
            if (first > 0 && nums[first] == nums[first - 1]){
                continue;
            }
            for (int second = first + 1; second < len - 2; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]){
                    continue;
                }

                for (int third = second + 1; third < len - 1; third++) {
                    int forth = len - 1;
                    if (third > second + 1 && nums[third] == nums[third - 1]){
                        continue;
                    }
                    System.err.println(third);
                    while (forth > third){
                        if (nums[first] + nums[second] + nums[third] + nums[forth] == target){
                            List<Integer> list = new ArrayList<Integer>();
                            list.add(nums[first]);
                            list.add(nums[second]);
                            list.add(nums[third]);
                            list.add(nums[forth]);
                            res.add(list);
                            break;
                        } else {
                            forth--;
                        }
                    }
                }
            }
        }
        return res;

    }
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        //       int[] ans = new int[13000];
        int ans = 100000;
        int res = 0;
        for (int start = 0; start < nums.length - 2; start++) {
            if (start > 0 && nums[start] == nums[start - 1]){
                continue;
            }
            int mid = start + 1,end = nums.length - 1;
            while (mid < end){
                int sum = nums[start] + nums[mid] + nums[end];
                int tmp = Math.abs(sum - target);
                if(sum < target){
                    if (ans > tmp){
                        ans = tmp;
                        res = sum;
                    }
                    mid++;
                }else if(sum > target){
                    if (ans > tmp){
                        ans = tmp;
                        res = sum;
                    }
                    end--;
                }else {
                    return sum;
                }
            }
        }

        return res;
    }
    public static List<List<Integer>> sumt(int[] nums){
        int s = 0;
        int e = nums.length - 1;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        threeSum1(nums,s,e,res);
        return res;
    }
    public static void threeSum1(int[] nums,int start,int end,List<List<Integer>> res) {

        if (nums.length < 3){
            return ;
        }
        while (start > 0 && nums[start] == nums[start - 1] && end -start > 1){
            start ++;
        }
        while (end < nums.length - 1 && nums[end] == nums[end + 1] && end -start > 1){
            end--;
        }
        if (end - start > 1){

            if(nums[start] + nums[end] + nums[end - 1] < 0){
                start++;
            }
            if(nums[start] + nums[start + 1] + nums[end] > 0){
                end--;
            }
            for (int i = start + 1; i < end; i++) {
                if(nums[start] + nums[i] + nums[end] == 0){
                    if (nums[start] == -3 && nums[end] == 3){
                        System.err.println(111);
                    }
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[start]);
                    list.add(nums[i]);
                    list.add(nums[end]);
                    if (!res.contains(list)){
                        res.add(list);
                        break;
                    }
                }
            }

            threeSum1(nums,start+1,end,res);
            threeSum1(nums,start,end-1,res);
        }

    }

    public static String longestCommonPrefix(String[] strs) {
        int minlen = 200;
        for (int i = 0; i < strs.length; i++) {
            if(strs[i].length() == 0){
                return "";
            }else {
                minlen = Math.min(strs[i].length(),minlen);
            }
        }
        int len = strs.length;
        String same = "";
        String res = "";
        boolean first = true;
        for (int i = minlen - 1; i >= 0; i--) {
            first = true;
            for (int j = 0; j < len; j++) {
                if(first){
                    same = strs[j].substring(0,i+1);
                }
                if(!same.equals(strs[j].substring(0,i+1))){
                    break;
                }else if(j == len - 1){
                    return  same;
                }
            }
        }

        return  res;
    }
    private static void sorte(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            findMax(arr, i);
        }
    }

    static void findMax(int[] arr, int i) {
        for (int j = i; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
            ;
        }
    }

    public static void swap(int[] arr, int min, int max) {
        int tmp = arr[max];
        arr[max] = arr[min];
        arr[min] = tmp;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + "");
        }
    }
}
